
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2136. -- CounterStrike -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2136: CounterStrike</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>27&nbsp;&nbsp;<span class=green>Solved: </span>22<br>[<a href='submitpage.php?id=2136'>Submit</a>][<a href='problemstatus.php?id=2136'>Status</a>][<a href='bbs.php?id=2136'>Discuss</a>]</center><h2>Description</h2><div class=content><p>1.管道从y轴负方向延伸到y轴正方向。 2.称x轴负方向为左边，x轴正方向为右边，z轴正方向为上边，z轴负方向为下边。 3.管道是由若干四棱柱拼接而成，每个四棱柱的两个底面都是边长为1的正方形，且这两个底面都平行于xoz平面。也就是说，对于管道的任何一个垂直于y轴的的截面，它都是正方形，只要知道右上角顶点的坐标(x,y,z)就可以知道正方形剩下三个点的坐标(x-1,y,z), (x,y,z-1), (x-1,y,z-1)。 4.知道了管道右上方的折线，通过向左平移1、再向下平移1、再向右平移1，再向上平移1，可以得到该管道的边界。所以给出管道右上方的折线的每个顶点的坐标，我们就可以确定整个管道的形状。 对于gx的枪，有如下说明: 1.gx的枪沿一条直线射出一颗子弹。我们把子弹视作是一个半径为r的圆，所以轨迹可以视作一个底面半径为r的狭长圆柱。对于某个y=y0的截面，如果子弹能够完整地通过，称此处是被gx控制的。反之，子弹在接触目标前会发生偏折，因此该截面是不被控制的。子弹刚好擦边而过的情况也算作可以通过。 2.gx站在y轴负方向的那一端，面向y轴正方向。gx的枪可以在管道外任何位置以任何角度，从y轴负方向向y轴正方向进行瞄准。 现在面对这个蜿蜒曲折的管道，gx想知道他能控制的最远截面的y坐标值是多少。</p></div><h2>Input</h2><div class=content><p>输入的第一行包含整数n和实数r。接下来n行每行三个实数，第i行的三个实数表示第i个正方形右上角顶点的坐标(x, y, z)。输入保证y坐标值是严格递增的。</p></div><h2>Output</h2><div class=content><p>输出一个实数，表示最远的控制点。保留三位小数。数据保证gx的子弹不能贯穿整个管道。</p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>【样例输入1】<br />
5 0<br />
0.0 -2.0 1.0<br />
0.0 0.0 1.0<br />
1.0 1.0 0.0<br />
0.0 1.5 1.0<br />
2.0 3.0 0.0<br />
【样例输出1】<br />
2.250<br />
【样例说明1】<br />
沿y轴正方向，最远可以控制到y=2.250<br />
（图示见问题描述）<br />
【样例输入2】<br />
3 0.2<br />
0.0 0.0 1.0<br />
0.0 1.0 1.0<br />
2.0 2.0 -1.0<br />
【样例输出2】<br />
1.374<br />
【数据范围】<br />
对于100%的数据 3≤n≤20000, 0≤r≤0.5, -100000≤xi, yi, zi≤100000<br />
均匀分布着50%的数据 r=0<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata></span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=By 高欣'>By 高欣</a></p></div><center>[<a href='submitpage.php?id=2136'>Submit</a>][<a href='problemstatus.php?id=2136'>Status</a>][<a href='bbs.php?id=2136'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
